/*
 * @Autor: taobo
 * @Date: 2020-06-14 12:50:28
 * @LastEditTime: 2020-06-14 12:56:30
 * @Description: leetcode 1300. 二分查找+脑筋急转弯
 */ 
// 给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，
// 数组的和最接近  target （最接近表示两者之差的绝对值最小）。
// 如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。请注意，答案不一定是 arr 中的数字。
//示例：
// 输入：arr = [4,9,3], target = 10
// 输出：3
// 解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int binary_search(vector<int>& arr,int tar){
        int l=0,r=arr.size()-1;
        while(l <=r){
            int mid = l+(r-l)/2;
            if(arr[mid]>=tar && (mid==0 || arr[mid-1]<tar))
                return mid;
            if(arr[mid]>=tar)
                r=mid-1;
            else
                l=mid+1;
        }
        return l;
    }
    //法一：枚举+二分查找
    // int findBestValue(vector<int>& arr, int target) {
    //     sort(arr.begin(),arr.end());
    //     int len = arr.size();
    //     vector<int> prefix(len+1,0);
    //     for(int i=1;i<=len;++i){
    //         prefix[i] = prefix[i-1]+arr[i-1];
    //     }
    //     int r = *max_element(arr.begin(),arr.end());
    //     int ans=0, diff=target;
    //     for(int x=1;x<=r;++x){
    //         int pos = binary_search(arr, x);
    //         int sum = prefix[pos]+x*(len-pos);
    //         // auto iter = lower_bound(arr.begin(), arr.end(), x);
    //         // int sum = prefix[iter-arr.begin()]+x*(arr.end()-iter);
    //         if(abs(sum-target)<diff){
    //             ans = x;
    //             diff = abs(sum-target);
    //         }
    //     }
    //     return ans;
    // }

    //法二：双重二分查找
    int findBestValue(vector<int>& arr, int target) {
        sort(arr.begin(),arr.end());
        int len = arr.size();
        vector<int> prefix(len+1,0);
        for(int i=1;i<=len;++i){
            prefix[i] = prefix[i-1]+arr[i-1];
        }
        int r = *max_element(arr.begin(),arr.end()) , l=0;
        int ans=-1;
        while(l <= r){
            int mid = l+(r-l)/2;
            int pos = binary_search(arr, mid);
            int sum = prefix[pos] + mid*(len-pos);
            if(sum<=target){
                ans = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        int p1=binary_search(arr, ans);
        int p2=binary_search(arr, ans+1);
        int small = prefix[p1]+ans*(len-p1);
        int big = prefix[p2]+(ans+1)*(len-p2);
        //  cout<<ans<<" " << p1<<p2;
        //  cout<<" "<<small<<" "<<big;
        return abs(target-small)>abs(big-target) ? ans+1 : ans;
    }
};

int main()
{
    Solution obj;
    vector<int> nums = {60864,25176,27249,21296,20204};
    int ans = obj.findBestValue(nums,56803);
    cout << ans<<endl;
    return 0;
}